{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Happy String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestDiverseString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长快乐字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果字符串中不含有任何 <code>&#39;aaa&#39;</code>，<code>&#39;bbb&#39;</code> 或 <code>&#39;ccc&#39;</code> 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。</p>\n",
    "\n",
    "<p>给你三个整数 <code>a</code>，<code>b</code> ，<code>c</code>，请你返回 <strong>任意一个</strong> 满足下列全部条件的字符串 <code>s</code>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s</code> 是一个尽可能长的快乐字符串。</li>\n",
    "\t<li><code>s</code> 中 <strong>最多</strong> 有<code>a</code> 个字母 <code>&#39;a&#39;</code>、<code>b</code>&nbsp;个字母 <code>&#39;b&#39;</code>、<code>c</code> 个字母 <code>&#39;c&#39;</code> 。</li>\n",
    "\t<li><code>s </code>中只含有 <code>&#39;a&#39;</code>、<code>&#39;b&#39;</code> 、<code>&#39;c&#39;</code> 三种字母。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果不存在这样的字符串 <code>s</code> ，请返回一个空字符串 <code>&quot;&quot;</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>a = 1, b = 1, c = 7\n",
    "<strong>输出：</strong>&quot;ccaccbcc&quot;\n",
    "<strong>解释：</strong>&quot;ccbccacc&quot; 也是一种正确答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>a = 2, b = 2, c = 1\n",
    "<strong>输出：</strong>&quot;aabbc&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>a = 7, b = 1, c = 0\n",
    "<strong>输出：</strong>&quot;aabaa&quot;\n",
    "<strong>解释：</strong>这是该测试用例的唯一正确答案。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= a, b, c &lt;= 100</code></li>\n",
    "\t<li><code>a + b + c &gt; 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-happy-string](https://leetcode.cn/problems/longest-happy-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-happy-string](https://leetcode.cn/problems/longest-happy-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n1\\n7', '7\\n1\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        res = ''\n",
    "        items = [[a, 'a'], [b, 'b'], [c, 'c']]\n",
    "        while True:\n",
    "            items.sort()\n",
    "            i = -1\n",
    "            # case not use last\n",
    "            if len(res) >= 2 and res[-2:] == items[-1][1] * 2:\n",
    "                if len(items) < 2 or items[-2][0] == 0:\n",
    "                    break\n",
    "                i = -2\n",
    "            if items[i][0] == 0:\n",
    "                break \n",
    "            res += items[i][1]\n",
    "            items[i][0] -= 1\n",
    "\n",
    "        return res\n",
    "            \n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        left = [a, b, c]\n",
    "        flag = [1, 1, 1]\n",
    "        ch = ['a', 'b', 'c']\n",
    "        res = ''\n",
    "        prev = -1\n",
    "        while True:\n",
    "            temp = [l * f for l, f in zip(left, flag)]\n",
    "            if sum(temp) == 0:\n",
    "                break\n",
    "            i = temp.index(max(temp))\n",
    "            res += ch[i]\n",
    "            left[i] -= 1\n",
    "            if i == prev:\n",
    "                flag[i] = 0\n",
    "            else:\n",
    "                flag = [1, 1, 1]\n",
    "            prev = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        c, last = collections.Counter({'a': a, 'b': b, 'c': c}), None\n",
    "        s = ''\n",
    "        while list(c.values()).count(0)<=1:\n",
    "            x, y = c.most_common(2)\n",
    "            if last == x[0]: \n",
    "                s += y[0]\n",
    "                c[y[0]]-=1\n",
    "                last = y[0]\n",
    "            else:\n",
    "                last = x[0]\n",
    "                if x[1]==1: \n",
    "                    s += x[0]\n",
    "                    c[x[0]] -= 1\n",
    "                else:\n",
    "                    s += x[0]*2\n",
    "                    c[x[0]] -= 2\n",
    "        x = c.most_common(1)[0]\n",
    "        if last != x[0]: s += x[0]*min(x[1], 2)\n",
    "        return s\n",
    "        \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        ans = []\n",
    "        ch_cnt = [ [a, 'a'], [b, 'b'], [c, 'c']]\n",
    "        while True:\n",
    "            ch_cnt.sort(key=lambda x: -x[0])\n",
    "            flag = False\n",
    "            for i,(cnt, ch) in enumerate(ch_cnt):\n",
    "                if cnt<=0:\n",
    "                    break\n",
    "                if len(ans)>=2 and ans[-1]==ch and ans[-2]==ch:\n",
    "                    continue\n",
    "\n",
    "                flag = True\n",
    "                ans.append(ch)\n",
    "                ch_cnt[i][0] -= 1\n",
    "                break\n",
    "            \n",
    "            if not flag:\n",
    "                return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        count = {'a':a, 'b':b, 'c':c}\n",
    "        res = \"\"\n",
    "        while True:\n",
    "            _, mid, most = sorted(count.keys(), key = lambda x: count[x])\n",
    "            if (len(res) < 2 or not res[-2] == res[-1] == most) and count[most]:\n",
    "                res += most\n",
    "                count[most] -= 1\n",
    "            elif count[mid]:\n",
    "                res += mid\n",
    "                count[mid] -= 1\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        ans=[]\n",
    "        cnt = [[a, 'a'], [b, 'b'], [c, 'c']]\n",
    "        while True:\n",
    "            cnt.sort(key=lambda x:-x[0])\n",
    "            check=False\n",
    "            for i,(c,ch) in enumerate(cnt):\n",
    "                if c<=0:\n",
    "                    break\n",
    "                if len(ans)>=2 and ans[-1]==ch and ans[-2]==ch:\n",
    "                    continue\n",
    "                check=True\n",
    "                cnt[i][0]-=1\n",
    "                ans.append(ch)\n",
    "                break\n",
    "            if not check:\n",
    "                return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        ans = ''\n",
    "        a = [[a,'a'],[b,'b'],[c,'c']]\n",
    "        while True:\n",
    "            hasNext = False\n",
    "            a.sort(reverse = True)\n",
    "            for i,(cnt,c) in enumerate(a):\n",
    "                if cnt == 0:\n",
    "                    break\n",
    "                if len(ans) >= 2 and ans[-1] == ans[-2] == c:\n",
    "                    continue\n",
    "                hasNext = True\n",
    "                ans += c\n",
    "                a[i][0] -= 1\n",
    "                break\n",
    "            if not hasNext:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from heapq import heappush\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:      \n",
    "        s = ''\n",
    "        if a == 0 and b == 0 and c == 0:\n",
    "            return s\n",
    "        \n",
    "        maxHeap = []\n",
    "        if a: heappush(maxHeap, [-a, 'a'])\n",
    "        if b: heappush(maxHeap, [-b, 'b'])\n",
    "        if c: heappush(maxHeap, [-c, 'c'])\n",
    "\n",
    "        while maxHeap:\n",
    "            countx, x = heappop(maxHeap)\n",
    "\n",
    "            # if string s already contains 2 consecutive characters xx , can't add one more x character\n",
    "            if len(s) >= 2 and s[-2:] == x*2:\n",
    "                # if max-heap is empty, return s \n",
    "                if not maxHeap:\n",
    "                    return s\n",
    "                # if max-heap is not empty, use the second largest amount of characters instead\n",
    "                else:\n",
    "                    county, y = heappop(maxHeap) \n",
    "                    s += y \n",
    "                    county += 1\n",
    "                    if county: \n",
    "                        heappush(maxHeap, [county, y])\n",
    "                    heappush(maxHeap, [countx, x])  # add tuple character x back to max-heap\n",
    "            # add character x to the end of the string\n",
    "            else:\n",
    "                s += x \n",
    "                countx += 1\n",
    "                if countx:\n",
    "                    heappush(maxHeap, [countx, x])\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        q = []\n",
    "        for cnt, ch in zip((-a, -b, -c), ('a', 'b', 'c')):\n",
    "            if cnt < 0:\n",
    "                q.append((cnt, ch))\n",
    "        heapify(q)\n",
    "\n",
    "        ans = []\n",
    "        while q:\n",
    "            cnt, ch = heappop(q)\n",
    "            # 当前值不能用的情况\n",
    "            if len(ans) >= 2 and ans[-1] == ans[-2] == ch:\n",
    "                # q中没有值了，没法继续\n",
    "                if not q:\n",
    "                    break\n",
    "                cnt2, ch2 = heappop(q)\n",
    "                ans.append(ch2)\n",
    "                cnt2 += 1\n",
    "                if cnt2 < 0:\n",
    "                    heappush(q, (cnt2, ch2))\n",
    "                heappush(q, (cnt, ch))\n",
    "            # 当前弹出可追加的情况\n",
    "            else:\n",
    "                ans.append(ch)\n",
    "                cnt += 1\n",
    "                if cnt < 0:\n",
    "                    heappush(q, (cnt, ch))\n",
    "        \n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        result = list()\n",
    "        count = [[a, 'a'], [b, 'b'], [c, 'c']]\n",
    "        while True:\n",
    "            count.sort(key=lambda x: (-x[0], x[1]))\n",
    "            has_next = False\n",
    "            for i, v in enumerate(count):\n",
    "                if v[0] <= 0:\n",
    "                    break\n",
    "                if len(result) >= 2 and result[-2] == result[-1] == v[1]:\n",
    "                    continue\n",
    "                result.append(v[1])\n",
    "                has_next = True\n",
    "                count[i][0] -= 1\n",
    "                break\n",
    "            if not has_next:\n",
    "                return ''.join(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        pq = []\n",
    "        if a:\n",
    "            pq.append((-a,'a'))\n",
    "        if b:\n",
    "            pq.append((-b,'b'))\n",
    "        if c:\n",
    "            pq.append((-c,'c'))\n",
    "        heapify(pq)\n",
    "        ans = ''\n",
    "        while pq:\n",
    "            tmp = []\n",
    "            while ans and pq and ans[-1] == pq[0][1]:\n",
    "                tmp.append(heappop(pq))\n",
    "            if not pq:\n",
    "                return ans\n",
    "            cnt,cur = heappop(pq)\n",
    "            cnt = -cnt\n",
    "            if tmp or cnt < 2: # 有更多的，就填一个\n",
    "                ans += cur\n",
    "                cnt -= 1\n",
    "            else:\n",
    "                ans += cur*2\n",
    "                cnt -= 2\n",
    "            if cnt:\n",
    "                heappush(pq,(-cnt,cur))\n",
    "            while tmp:\n",
    "                heappush(pq,tmp.pop())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        count = {'a': a, 'b': b, 'c': c}  \n",
    "        res = ''  \n",
    "        while True:\n",
    "            _, mid, most = sorted(count.keys(), key=lambda x: count[x])  # 按照剩余数量排序，取出最多和次多的字母\n",
    "            # 当最多的字母还有时，且结果字符串长度小于2或者最后两个字符不全为most，均可使用most\n",
    "            if (len(res) < 2 or not res[-2] == res[-1] == most) and count[most]:\n",
    "                res += most  # 接在结果后面\n",
    "                count[most] -= 1  # 数量减一\n",
    "            elif count[mid]:  # 否则使用次多的字母mid(进入这个elif,意味着结尾两个字符必然为most,故只需要mid字符还有就可以用)\n",
    "                res += mid  # 接在结果后面\n",
    "                count[mid] -= 1  # 数量减一\n",
    "            else:  # 没有字母可以用了，结束\n",
    "                break\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        #两个连续处理，错！！！\n",
    "        \"\"\" stack = [[-a,'a'],[-b,'b'],[-c,'c']]\n",
    "        heapq.heapify(stack)\n",
    "        pre = ''\n",
    "        ans = []\n",
    "        while stack:\n",
    "            \n",
    "            v, k = heapq.heappop(stack)\n",
    "            if k == pre:\n",
    "                #if not stack:\n",
    "                    #return \"\"\n",
    "                v2,k2 = heapq.heappop(stack)\n",
    "                ans.append(k2)\n",
    "                pre = k2\n",
    "                v2 += 1\n",
    "                heapq.heappush(stack,[v2,k2])\n",
    "                heapq.heappush(stack,[v,k])\n",
    "            else:\n",
    "                ans.append(k)\n",
    "                v += 1\n",
    "                pre = k\n",
    "                if v >= 1:\n",
    "                    v, k = heapq.heappop(stack)\n",
    "                    pre = k\n",
    "                    ans.append(k)\n",
    "                    v += 1\n",
    "                if v:\n",
    "                    heapq.heappush(stack,[v,k])\n",
    "        return ''.join(ans) \"\"\"\n",
    "        #stack = [[-a,'a'],[-b,'b'],[-c,'c']]\n",
    "        stack = []\n",
    "        if a > 0:\n",
    "            stack.append([-a,'a'])\n",
    "        if b > 0:\n",
    "            stack.append([-b,'b'])\n",
    "        if c > 0:\n",
    "            stack.append([-c,'c'])\n",
    "        heapq.heapify(stack)\n",
    "        pre1 = ''\n",
    "        pre2 = ''\n",
    "        ans = []\n",
    "        while stack:\n",
    "            v, k = heapq.heappop(stack)\n",
    "            if k == pre1 and k == pre2:\n",
    "                if not stack:\n",
    "                    return ''.join(ans)\n",
    "                v2,k2 = heapq.heappop(stack)\n",
    "                ans.append(k2)\n",
    "                v2 += 1\n",
    "                pre1,pre2 = pre2,k2\n",
    "                if v2:\n",
    "                    heapq.heappush(stack,[v2,k2])\n",
    "                heapq.heappush(stack,[v,k])\n",
    "            else:\n",
    "                ans.append(k)\n",
    "                v += 1\n",
    "                pre1,pre2 = pre2,k\n",
    "                if v:\n",
    "                    heapq.heappush(stack,[v,k])\n",
    "        return ''.join(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        num_map = {'a': a, 'b': b, 'c': c}\n",
    "        res = ''\n",
    "        while True:\n",
    "            # 贪心法-动态获取当前剩余字符里面的最大与中间的使用 less, mid, most 三个字符会实时变化\n",
    "            less, mid, most = sorted(num_map.keys(), key=lambda x: num_map[x])\n",
    "            # print(less, mid, most)\n",
    "            if (len(res) < 2 or not res[-2] == res[-1] == most) and num_map[most] > 0:\n",
    "                res += most\n",
    "                num_map[most] -= 1 \n",
    "            elif (not res[-2] == res[-1] == mid) and num_map[mid] > 0:\n",
    "                res += mid\n",
    "                num_map[mid] -= 1\n",
    "            else:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        h = []\n",
    "        if a: heappush(h, [-a, 'a'])\n",
    "        if b: heappush(h, [-b, 'b'])\n",
    "        if c: heappush(h, [-c, 'c'])\n",
    "        ans = []\n",
    "        while h:\n",
    "            cnt, ch = heappop(h)\n",
    "\n",
    "            if len(ans) >= 2 and ch == ans[-1] == ans[-2]:\n",
    "                if not h: break\n",
    "                cnt2, ch2 = heappop(h)\n",
    "                heappush(h, [cnt, ch])\n",
    "                cnt, ch = cnt2, ch2\n",
    "\n",
    "            ans.append(ch)\n",
    "            if cnt + 1:\n",
    "                heappush(h, [cnt + 1, ch])\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        res = \"\"\n",
    "        mheap = []\n",
    "        if a!=0: mheap.append((-a,'a'))\n",
    "        if b!=0: mheap.append((-b,'b'))\n",
    "        if c!=0: mheap.append((-c,'c'))\n",
    "        heapq.heapify(mheap)\n",
    "        while mheap:\n",
    "            r1,c1 = heapq.heappop(mheap)\n",
    "            if len(res)>=2 and res[-1]==c1 and res[-2]==c1:\n",
    "                if mheap:\n",
    "                    r2,c2 = heapq.heappop(mheap)\n",
    "                    res = res + c2\n",
    "                    r2 += 1\n",
    "                    if not r2 == 0 :\n",
    "                        heapq.heappush(mheap, (r2, c2))\n",
    "                    heapq.heappush(mheap, (r1, c1))\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                res = res + c1\n",
    "                r1 += 1\n",
    "                if not r1 == 0:\n",
    "                    heapq.heappush(mheap, (r1, c1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        res = ''\n",
    "        removeZero = lambda num,char: num > 0\n",
    "        items = [[a, 'a'], [b, 'b'], [c, 'c']]\n",
    "        while True:\n",
    "            items.sort()\n",
    "            i = -1\n",
    "            # case not use last\n",
    "            if len(res) >= 2 and res[-2:] == items[-1][1] * 2:\n",
    "                if len(items) < 2 or items[-2][0] == 0:\n",
    "                    break\n",
    "                i = -2\n",
    "            if items[i][0] == 0:\n",
    "                break \n",
    "            res += items[i][1]\n",
    "            items[i][0] -= 1\n",
    "\n",
    "        return res\n",
    "            \n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from heapq import heappush\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:      \n",
    "        s = ''\n",
    "        if a == 0 and b == 0 and c == 0:\n",
    "            return s\n",
    "        \n",
    "        maxHeap = []\n",
    "        if a: heappush(maxHeap, [-a, 'a'])\n",
    "        if b: heappush(maxHeap, [-b, 'b'])\n",
    "        if c: heappush(maxHeap, [-c, 'c'])\n",
    "\n",
    "        while maxHeap:\n",
    "            countx, x = heappop(maxHeap)\n",
    "\n",
    "            # if string s already contains 2 consecutive characters xx , can't add one more x character\n",
    "            if len(s) >= 2 and s[-2:] == x*2:\n",
    "                # if max-heap is empty, return s \n",
    "                if not maxHeap:\n",
    "                    break\n",
    "                # if max-heap is not empty, use the second largest amount of characters instead\n",
    "                else:\n",
    "                    county, y = heappop(maxHeap) \n",
    "                    s += y \n",
    "                    county += 1\n",
    "                    if county: \n",
    "                        heappush(maxHeap, [county, y])\n",
    "                    heappush(maxHeap, [countx, x])  # add tuple character x back to max-heap\n",
    "            # add character x to the end of the string\n",
    "            else:\n",
    "                s += x \n",
    "                countx += 1\n",
    "                if countx:\n",
    "                    heappush(maxHeap, [countx, x])\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        left = [a, b, c]\n",
    "        flag = [1, 1, 1]\n",
    "        ch = ['a', 'b', 'c']\n",
    "        res = ''\n",
    "        prev = -1\n",
    "        while True:\n",
    "            temp = [l * f for l, f in zip(left, flag)]\n",
    "            if sum(temp) == 0:\n",
    "                break\n",
    "            i = temp.index(max(temp))\n",
    "            res += ch[i]\n",
    "            left[i] -= 1\n",
    "            if i == prev:\n",
    "                flag[i] = 0\n",
    "            else:\n",
    "                flag = [1, 1, 1]\n",
    "            prev = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        dict = {'a':a,'b':b,'c':c}\n",
    "        res = ''\n",
    "\n",
    "        while True:\n",
    "            most,mid,less = sorted(dict.keys(),key=lambda x:dict[x],reverse=True)\n",
    "            if (len(res)<2 or not res[-2] == res[-1] == most) and dict[most] != 0 :\n",
    "                res += most\n",
    "                dict[most] -= 1\n",
    "            elif not res[-2] == res[-1] == mid and dict[mid] != 0:\n",
    "                res += mid\n",
    "                dict[mid] -= 1\n",
    "            else:\n",
    "                return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 通过时间：35.12.06，贪心策略没选对盲目计算每个字母数量了\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        charque = PriorityQueue()\n",
    "        charque.put((-a, 'a'))\n",
    "        charque.put((-b, 'b'))\n",
    "        charque.put((-c, 'c'))\n",
    "        res = ''\n",
    "        while charque.empty() == False:\n",
    "            nowlist = []\n",
    "            now1 = charque.get()\n",
    "            now2 = charque.get()\n",
    "            now3 = charque.get()\n",
    "            # print(now1, now2, now3, res)\n",
    "            if len(res) < 2 or (len(res) >= 2 and not (res[-1] == now1[1] and res[-2] == now1[1]) and -now1[0] > 0):\n",
    "                keynum = -now1[0]\n",
    "                if keynum > 0:\n",
    "                    res += now1[1]\n",
    "                    keynum -= 1\n",
    "                charque.put((-keynum, now1[1]))\n",
    "                charque.put(now2)\n",
    "                charque.put(now3)\n",
    "            elif not (res[-1] == now2[1] and res[-2] == now2[1]) and -now2[0] > 0:\n",
    "                keynum = -now2[0]\n",
    "                if keynum > 0:\n",
    "                    res += now2[1]\n",
    "                    keynum -= 1\n",
    "                charque.put(now1)\n",
    "                charque.put((-keynum, now2[1]))\n",
    "                charque.put(now3)\n",
    "            elif not (res[-1] == now3[1] and res[-2] == now3[1]) and -now3[0] > 0:\n",
    "                keynum = -now3[0]\n",
    "                if keynum > 0:\n",
    "                    res += now3[1]\n",
    "                    keynum -= 1\n",
    "                charque.put(now1)\n",
    "                charque.put(now2)\n",
    "                charque.put((-keynum, now3[1]))\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        sortdValueList = sorted(Counter({'a': a, 'b': b, 'c': c}).items(), key=lambda x: -x[1])\n",
    "        n = math.ceil(max(a, b, c) / 2) # 桶的数量\n",
    "        bucket = [[] for _ in range(n)]\n",
    "        i = 0 # 遍历桶的序号\n",
    "        maxC = sortdValueList[0][0]\n",
    "        for k, v in sortdValueList:\n",
    "            curCcount = v\n",
    "            while curCcount > 0:\n",
    "                curBucketIndex = i % n\n",
    "                bucket[curBucketIndex].append(k)\n",
    "                curCcount -= 1\n",
    "                i += 1\n",
    "            if maxC == k: # 次长字符需要从头开始装\n",
    "                i = 0\n",
    "        ans = \"\"\n",
    "        for b in bucket:\n",
    "            if ans and b[0][0] == ans[-1]:\n",
    "                break\n",
    "            ans += \"\".join(b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        ans = []\n",
    "        cnt = [[a, 'a'], [b, 'b'], [c, 'c']]\n",
    "        while True:\n",
    "            cnt.sort(key=lambda x: -x[0])\n",
    "            hasNext = False\n",
    "            for i, (c, ch) in enumerate(cnt):\n",
    "                if c <= 0:\n",
    "                    break\n",
    "                if len(ans) >= 2 and ans[-2] == ch and ans[-1] == ch:\n",
    "                    continue\n",
    "                hasNext = True\n",
    "                ans.append(ch)\n",
    "                cnt[i][0] -= 1\n",
    "                break\n",
    "            if not hasNext:\n",
    "                return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        cnt = [[a,'a'],[b,'b'],[c,'c']]\n",
    "        \n",
    "        ans = []\n",
    "        while True:\n",
    "            # 按照数量大小排序\n",
    "            cnt.sort(key = lambda x:-x[0])\n",
    "            hasNext = False\n",
    "            # 开始从大到小选择字符（选择了，说明hasNext=True,否则就为False）\n",
    "            for i,(c,ch) in enumerate(cnt):\n",
    "                if c <= 0:break\n",
    "                if len(ans) >= 2 and ans[-1] == ch and ans[-2] == ch:continue\n",
    "                hasNext = True\n",
    "                ans.append(ch)\n",
    "                cnt[i][0] -= 1\n",
    "                break\n",
    "            # 没有选择过字符说明选择完毕\n",
    "            if not hasNext:\n",
    "                return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        s = a + b + c\n",
    "        t = [(-a, 'a'), (-b, 'b'), (-c, 'c')]\n",
    "        heapify(t)\n",
    "        last = \"\"\n",
    "        cnt = 0\n",
    "        ans = \"\"\n",
    "        while t:\n",
    "            cur = heappop(t)\n",
    "            if cur[0] == 0: break\n",
    "            if cur[0] <= -2 and -cur[0] >= s + cur[0] + 1:\n",
    "\n",
    "                if t and t[0][0] <= -1:\n",
    "                    temp = heappop(t)\n",
    "                    ans += cur[1] * 2 + temp[1]\n",
    "                    heappush(t, (temp[0] + 1, temp[1]))\n",
    "                    last = temp[1]\n",
    "                    cnt = 1\n",
    "                else:\n",
    "                    if cur[1] != last or (cur[1] == last and cnt != 2):\n",
    "                        ans += cur[1] * (2 - cnt * int(cur[1] == last))\n",
    "                        break\n",
    "                    last = cur[1]\n",
    "                    cnt = 2\n",
    "\n",
    "                heappush(t, (cur[0] + 2, cur[1]))\n",
    "                s -= 3\n",
    "            else:\n",
    "                if last == cur[1] and cnt == 2:\n",
    "                    if t and t[0][0] <= -1:\n",
    "                        temp = heappop(t)\n",
    "                        ans += temp[1]\n",
    "                        heappush(t, (temp[0] + 1, temp[1]))\n",
    "                        last = temp[1]\n",
    "                    else:\n",
    "                        break\n",
    "                if cur[1] == last:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cnt = 1\n",
    "                last = cur[1]\n",
    "                ans += cur[1]\n",
    "                heappush(t, (cur[0] + 1, cur[1]))\n",
    "                s -= 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        ma = max(a,b,c)\n",
    "        ma = min(((a+b+c-ma)+1)*2,ma)\n",
    "        space = ['']*(ma-1)\n",
    "        p = 0\n",
    "        if a >= b and a >= c:\n",
    "            for _ in range(b):\n",
    "                space[p % (ma - 1)] = space[p % (ma - 1)] + 'b'\n",
    "                p += 1\n",
    "            for _ in range(c):\n",
    "                space[p % (ma - 1)] = space[p % (ma - 1)] + 'c'\n",
    "                p += 1\n",
    "            if p >= ma - 1:\n",
    "                return 'a' + 'a'.join(space) + 'a'\n",
    "            else:\n",
    "                pp = 0\n",
    "                while ma and pp < p:\n",
    "                    space[pp] = space[pp] + 'a'\n",
    "                    ma -= 1\n",
    "                    pp += 1\n",
    "                pp = 0\n",
    "                while ma and pp < p:\n",
    "                    space[pp] = 'a' + space[pp]\n",
    "                    ma -= 1\n",
    "                    pp += 1\n",
    "                if ma == 2:\n",
    "                    return 'a' + ''.join(space[:p]) +'a'\n",
    "                elif ma == 1:\n",
    "                    return 'a' + ''.join(space[:p])\n",
    "                else:\n",
    "                    return ''.join(space[:p])\n",
    "        \n",
    "        elif b >= a and b >= c:\n",
    "            for _ in range(a):\n",
    "                space[p % (ma - 1)] = space[p % (ma - 1)] + 'a'\n",
    "                p += 1\n",
    "            for _ in range(c):\n",
    "                space[p % (ma - 1)] = space[p % (ma - 1)] + 'c'\n",
    "                p += 1\n",
    "            if p >= ma - 1:\n",
    "                return 'b' + 'b'.join(space) + 'b'\n",
    "            else:\n",
    "                pp = 0\n",
    "                while ma and pp < p:\n",
    "                    space[pp] = space[pp] + 'b'\n",
    "                    ma -= 1\n",
    "                    pp += 1\n",
    "                pp = 0\n",
    "                while ma and pp < p:\n",
    "                    space[pp] = 'b' + space[pp]\n",
    "                    ma -= 1\n",
    "                    pp += 1\n",
    "                if ma == 2:\n",
    "                    return 'b' + ''.join(space[:p]) +'b'\n",
    "                elif ma == 1:\n",
    "                    return 'b' + ''.join(space[:p])\n",
    "                else:\n",
    "                    return ''.join(space[:p])\n",
    "\n",
    "        elif c >= a and c >= b:\n",
    "            for _ in range(a):\n",
    "                space[p % (ma - 1)] = space[p % (ma - 1)] + 'a'\n",
    "                p += 1\n",
    "            for _ in range(b):\n",
    "                space[p % (ma - 1)] = space[p % (ma - 1)] + 'b'\n",
    "                p += 1\n",
    "            if p >= ma - 1:\n",
    "                return 'c' + 'c'.join(space) + 'c'\n",
    "            else:\n",
    "                pp = 0\n",
    "                while ma and pp < p:\n",
    "                    space[pp] = space[pp] + 'c'\n",
    "                    ma -= 1\n",
    "                    pp += 1\n",
    "                pp = 0\n",
    "                while ma and pp < p:\n",
    "                    space[pp] = 'c' + space[pp]\n",
    "                    ma -= 1\n",
    "                    pp += 1\n",
    "                if ma == 2:\n",
    "                    return 'c' + ''.join(space[:p]) +'c'\n",
    "                elif ma == 1:\n",
    "                    return 'c' + ''.join(space[:p])\n",
    "                else:\n",
    "                    return ''.join(space[:p])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        res = \"\"\n",
    "        a, b, c = [\"a\", a], [\"b\", b], [\"c\", c]\n",
    "        def sort(a, b, c):\n",
    "            if a[1] < b[1]:\n",
    "                a, b = b, a\n",
    "            if a[1] < c[1]:\n",
    "                a, c = c, a\n",
    "            if b[1] < c[1]:\n",
    "                b, c = c, b\n",
    "            return a, b, c\n",
    "        a, b, c = sort(a, b, c)\n",
    "        \n",
    "        while a[1] or b[1] or c[1]:\n",
    "            if len(res) >= 2 and res[-1] == res[-2] == a[0]:\n",
    "                if b[1] == 0:\n",
    "                    break\n",
    "                res += b[0]\n",
    "                b[1] -= 1\n",
    "            else:\n",
    "                if a[1] == 0:\n",
    "                    break\n",
    "                res += a[0]\n",
    "                a[1] -= 1\n",
    "            a, b, c = sort(a, b, c)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        heap = []\n",
    "        for cnt,char in [(-a, \"a\"), (-b, \"b\"), (-c, \"c\")]:\n",
    "            if cnt!=0:\n",
    "                heapq.heappush(heap,(cnt,char))\n",
    "        res = \"\"\n",
    "        \n",
    "        while heap:\n",
    "            cnt, char = heapq.heappop(heap)\n",
    "            \n",
    "            if len(res)>1 and res[-1] == res[-2] == char:\n",
    "                if not heap:\n",
    "                    break\n",
    "                cnt2, char2 = heapq.heappop(heap)\n",
    "                res+= char2\n",
    "                cnt2+=1\n",
    "                if cnt2:\n",
    "                    heapq.heappush(heap,(cnt2,char2))\n",
    "            else:\n",
    "                res+= char\n",
    "                cnt+=1\n",
    "            if cnt:\n",
    "                heapq.heappush(heap,(cnt,char))\n",
    "            \n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        r = ['', '']\n",
    "        q = queue.PriorityQueue()\n",
    "        q.put((-a, 'a'))\n",
    "        q.put((-b, 'b'))\n",
    "        q.put((-c, 'c'))\n",
    "        while not q.empty():\n",
    "            temp = []\n",
    "            while not q.empty():\n",
    "                n, c = q.get()\n",
    "                if not (r[-1] == c and r[-2] == c) and n < 0:\n",
    "                    r.append(c)\n",
    "                    temp.append((n+1, c))\n",
    "                    for t in temp:\n",
    "                        q.put(t)\n",
    "                    break\n",
    "                else:\n",
    "                    temp.append((n, c))\n",
    "        return ''.join(r)\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        res=''\n",
    "        abcmap=[['a',a],['b',b],['c',c]]\n",
    "        while True:\n",
    "            abcmap.sort(key = lambda abcitem:abcitem[1])\n",
    "            less,mid,most = abcmap[0][0],abcmap[1][0],abcmap[2][0]\n",
    "            if (len(res)<2 or not res[-2]==res[-1]==most) and abcmap[2][1]>0:\n",
    "                res +=most\n",
    "                abcmap[2][1] -=1\n",
    "            elif (not res[-2] == res[-1]==mid )and abcmap[1][1]>0:\n",
    "                res += mid\n",
    "                abcmap[1][1] -=1\n",
    "            else:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        import queue\n",
    "        q = queue.PriorityQueue()\n",
    "        if a  > 0:\n",
    "            q.put([-a,\"a\"])\n",
    "        if b > 0:\n",
    "            q.put([-b,\"b\"])\n",
    "        if c > 0:\n",
    "            q.put([-c,\"c\"])\n",
    "        res = \"\"\n",
    "        pre_num = 0\n",
    "        pre_chr = \"\"\n",
    "        while not q.empty():\n",
    "            n,ch = q.get()\n",
    "            n = -n\n",
    "            if ch == pre_chr:\n",
    "                pre_num += 1\n",
    "            else:\n",
    "                pre_num = 1\n",
    "                pre_chr = ch\n",
    "            if pre_num == 3:\n",
    "                if q.empty():\n",
    "                    break\n",
    "                n2,ch2 = q.get()\n",
    "                n2 = -n2\n",
    "                res += ch2\n",
    "                n2 -= 1\n",
    "                pre_num = 1\n",
    "                pre_chr = ch2\n",
    "                q.put([-n,ch])\n",
    "                if n2 > 0:\n",
    "                    q.put([-n2,ch2])\n",
    "            else:\n",
    "                res += ch\n",
    "                n -= 1\n",
    "                if n > 0:\n",
    "                    q.put([-n,ch])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        优先队列 + 贪心思路\n",
    "        优先处理abc 数量最多的一个\n",
    "        用两个变量cnt, pre 分别记录上一个字符连续出现的次数cnt 和上一个选择的字符pre\n",
    "        当cnt == 2 并且 pre == cur.ch时 需要弹出next字符进行拼接\n",
    "    '''\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        pq = []\n",
    "        if a: pq.append((-a, 'a'))\n",
    "        if b: pq.append((-b, 'b'))\n",
    "        if c: pq.append((-c, 'c'))\n",
    "        heapify(pq)\n",
    "        ans = []\n",
    "        cnt = 0\n",
    "        pre_char = ''\n",
    "        while len(pq):\n",
    "            val, char = heappop(pq)\n",
    "            if cnt == 2 and pre_char == char:\n",
    "                if len(pq) < 1: break\n",
    "                next_val, next_char = heappop(pq)\n",
    "                ans.append(next_char)\n",
    "                pre_char = next_char\n",
    "                next_val += 1\n",
    "                if -next_val > 0: heappush(pq, (next_val, next_char))\n",
    "                cnt = 1\n",
    "            else:\n",
    "                ans.append(char)\n",
    "                if pre_char != char: cnt = 1\n",
    "                else: cnt += 1\n",
    "                pre_char = char\n",
    "                val += 1\n",
    "            if -val > 0: heappush(pq, (val, char))\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        ans = []\n",
    "        array = [a, b, c]\n",
    "        while True:\n",
    "            t = sorted([(x, i) for i, x in enumerate(array)], reverse=True)\n",
    "            if len(ans) >= 2 and t[0][1] == ans[-1] == ans[-2]:\n",
    "                if t[1][0] == 0:\n",
    "                    break\n",
    "                ans.append(t[1][1])\n",
    "                array[t[1][1]] -= 1\n",
    "            else:\n",
    "                if t[0][0] == 0:\n",
    "                    break\n",
    "                ans.append(t[0][1])\n",
    "                array[t[0][1]] -= 1\n",
    "        d = {0: 'a', 1: 'b', 2: 'c'}\n",
    "        ans = ''.join([d[x] for x in ans])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\r\n",
    "        # 贪心算法，每次添加一个字母\r\n",
    "        mm = {'a':a, 'b':b, 'c':c}\r\n",
    "        ret = []\r\n",
    "        while True:\r\n",
    "            # 键值降序的字典\r\n",
    "            mm = dict(sorted(mm.items(), key=lambda kv: kv[1], reverse=True))\r\n",
    "            is_end = True\r\n",
    "            for k in mm.keys():\r\n",
    "                if (mm[k] == 0 or (len(ret) >= 2 and ret[-1] == k and ret[-2] == k)):\r\n",
    "                    continue\r\n",
    "                ret.append(k)\r\n",
    "                mm[k] -= 1\r\n",
    "                is_end = False\r\n",
    "                break\r\n",
    "            if is_end: \r\n",
    "                break\r\n",
    "        return \"\".join(ret)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        sortdValueList = sorted(Counter({'a': a, 'b': b, 'c': c}).items(), key=lambda x: -x[1])\n",
    "        # print(f\"sortdValueList: {sortdValueList}\")\n",
    "        n = math.ceil(max(a, b, c) / 2) # 桶的数量\n",
    "        bucket = [[] for _ in range(n)]\n",
    "        i = 0\n",
    "        maxC = sortdValueList[0][0]\n",
    "        for k, v in sortdValueList:\n",
    "            curCcount = v\n",
    "            while curCcount > 0:\n",
    "                curBucketIndex = i % n\n",
    "                # print(f\"curBucketIndex: {curBucketIndex}\")\n",
    "                curBucket = bucket[curBucketIndex]\n",
    "                addStr = ''\n",
    "                addStr = k\n",
    "                curCcount -= 1\n",
    "                curBucket.append(addStr)\n",
    "                bucket[curBucketIndex] = curBucket[::]\n",
    "                i += 1\n",
    "            if maxC == k:\n",
    "                i = 0\n",
    "            \n",
    "            print(f\"k:{k}, v: {v}, bucket: {bucket}\")\n",
    "        ans = \"\"\n",
    "        for b in bucket:\n",
    "            if ans and b[0][0] == ans[-1]:\n",
    "                break\n",
    "            ans += \"\".join(b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        num_map = {'a': a, 'b': b, 'c': c}\n",
    "        res = ''\n",
    "        while True:\n",
    "            less, mid, most = sorted(num_map.keys(), key = lambda x:num_map[x])\n",
    "            if (len(res) < 2 or not res[-2] == res[-1] == most) and num_map[most] > 0:\n",
    "                res += most\n",
    "                num_map[most] -= 1\n",
    "            elif (not res[-2] == res[-1] == mid) and num_map[mid] > 0:\n",
    "                res += mid\n",
    "                num_map[mid] -= 1\n",
    "            else:\n",
    "                return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\r\n",
    "        # 贪心算法\r\n",
    "        mm = {'a':a, 'b':b, 'c':c}\r\n",
    "        ret = []\r\n",
    "        while True:\r\n",
    "            # 键值降序的字典\r\n",
    "            mm = dict(sorted(mm.items(), key=lambda kv: kv[1], reverse=True))\r\n",
    "            is_end = True\r\n",
    "            for k in mm.keys():\r\n",
    "                if (mm[k]==0 or (len(ret)>=2 and ret[-1]==k and ret[-2]==k)):\r\n",
    "                    continue\r\n",
    "                ret.append(k)\r\n",
    "                mm[k] -= 1\r\n",
    "                is_end = False\r\n",
    "                break\r\n",
    "            if is_end: \r\n",
    "                break\r\n",
    "        return \"\".join(ret)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\r\n",
    "\r\n",
    "        res = []\r\n",
    "        # 每次优先尝试最多的能不能使用， 可以就用，不可以就用第二大\r\n",
    "        while a or b or c:\r\n",
    "            mx = max(a, b, c)\r\n",
    "            if a == mx: \r\n",
    "                if not (len(res) >= 2 and res[-1] == 'a' and res[-2] == 'a'):\r\n",
    "                    res.append('a')\r\n",
    "                    a -= 1\r\n",
    "                else:\r\n",
    "                    if max(b, c) == 0:\r\n",
    "                        break \r\n",
    "                    if b > c:\r\n",
    "                        res.append('b')\r\n",
    "                        b -= 1\r\n",
    "                    else:\r\n",
    "                        res.append('c')\r\n",
    "                        c -= 1\r\n",
    "            elif b == mx:\r\n",
    "                if len(res) < 2 or res[-1] != 'b' or res[-2] != 'b':\r\n",
    "                    res.append('b') \r\n",
    "                    b -= 1\r\n",
    "                else:\r\n",
    "                    if max(a, c) == 0:\r\n",
    "                        break \r\n",
    "                    if a > c:\r\n",
    "                        res.append('a')\r\n",
    "                        a -= 1\r\n",
    "                    else:\r\n",
    "                        res.append('c')\r\n",
    "                        c -= 1\r\n",
    "            else:\r\n",
    "                if len(res) < 2 or res[-1] != 'c' or res[-2] != 'c':\r\n",
    "                    res.append('c')\r\n",
    "                    c -= 1\r\n",
    "                else:\r\n",
    "                    if max(a, b) == 0:\r\n",
    "                        break \r\n",
    "                    if a > b:\r\n",
    "                        res.append('a')\r\n",
    "                        a -= 1\r\n",
    "                    else:\r\n",
    "                        res.append('b')\r\n",
    "                        b -= 1\r\n",
    "        return \"\".join(res)\r\n",
    "            \r\n",
    "\r\n",
    "             \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\r\n",
    "        mm = {'a':a, 'b':b, 'c':c}\r\n",
    "        ret = []\r\n",
    "        while True:\r\n",
    "            mm = dict(sorted(mm.items(), key=lambda kv: kv[1], reverse=True))\r\n",
    "            is_end = True\r\n",
    "            for k in mm.keys():\r\n",
    "                if (mm[k]==0 or (len(ret)>=2 and ret[-1]==k and ret[-2]==k)):\r\n",
    "                    continue\r\n",
    "                ret.append(k)\r\n",
    "                mm[k] -= 1\r\n",
    "                is_end = False\r\n",
    "                break\r\n",
    "            if is_end: break\r\n",
    "        return \"\".join(ret)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "\n",
    "        data = [[a, 'a'], [b, 'b'], [c, 'c']]\n",
    "        ans = []\n",
    "        prelen = 0\n",
    "        while True:\n",
    "            data.sort(key=lambda x:x[0], reverse=True)\n",
    "            for i , (cnt ,c) in enumerate(data):\n",
    "                if cnt <= 0:\n",
    "                    continue\n",
    "                if len(ans) >= 2 and ans[-2]==c and ans[-1] == c:\n",
    "                    continue\n",
    "\n",
    "                ans.append(c)\n",
    "                data[i][0] -= 1\n",
    "                break\n",
    "\n",
    "            if len(ans) == prelen: break\n",
    "            \n",
    "            prelen = len(ans)\n",
    "\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        ans=[]\n",
    "        cnt=[[a,'a'],[b,'b'],[c,'c']]\n",
    "        while True:\n",
    "            cnt.sort(key=lambda x:-x[0])\n",
    "            hasNext=False\n",
    "            for i,(c,ch) in enumerate(cnt):\n",
    "                if c<=0:\n",
    "                    break\n",
    "                if len(ans)>=2 and ans[-2]==ch and ans[-1]==ch:\n",
    "                    continue\n",
    "                hasNext=True\n",
    "                ans.append(ch)\n",
    "                cnt[i][0]-=1\n",
    "                break\n",
    "            if not hasNext:\n",
    "                return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 最长快乐字符串，贪心，输入：a = 1, b = 1, c = 7输出：\"ccaccbcc\"\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        count = {'a': a, 'b': b, 'c': c}\n",
    "        ans = ''\n",
    "        while True:\n",
    "            least, mid, most = sorted(count.keys(), key=lambda x: count[x])\n",
    "            if (len(ans) < 2 or not ans[-2] == ans[-1] == most) and count[most]:\n",
    "                ans += most\n",
    "                count[most] -= 1\n",
    "            elif count[mid]:\n",
    "                ans += mid\n",
    "                count[mid] -= 1\n",
    "            else:break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        ans = []\n",
    "        cnt = [[a, 'a'], [b, 'b'], [c, 'c']]\n",
    "        while True:\n",
    "            cnt.sort(key=lambda x: -x[0])\n",
    "            hasNext = False\n",
    "            for i, (c, ch) in enumerate(cnt):\n",
    "                if c <= 0:\n",
    "                    break\n",
    "                if len(ans) >= 2 and ans[-2] == ch and ans[-1] == ch:\n",
    "                    continue\n",
    "                hasNext = True\n",
    "                ans.append(ch)\n",
    "                cnt[i][0] -= 1\n",
    "                break\n",
    "            if not hasNext:\n",
    "                return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        load = []\n",
    "        # heappush(load, {-a, 'a'})\n",
    "        # heappush(load, (-b, 'b'))\n",
    "        # heappush(load, (-c, 'c'))\n",
    "        # d = dict()\n",
    "        # d['a'], d['b'], d['c'] = a, b, c\n",
    "        d = [['a', a], ['b', b], ['c', c]]\n",
    "        \n",
    "        res = []\n",
    "        while True:\n",
    "            # d = dict(d.items(), key = lambda x:x[1], reverse = True)\n",
    "            d.sort(key = lambda x: x[1], reverse = True)\n",
    "            find = False\n",
    "            emptyCnt = 0\n",
    "            for i, (k, v) in enumerate(d):\n",
    "                # print(v, emptyCnt)\n",
    "                if v <= 0 and emptyCnt == 2:\n",
    "                    break\n",
    "                if v <= 0 and emptyCnt < 2:\n",
    "                    emptyCnt += 1\n",
    "                    continue\n",
    "                if len(res) >= 2 and res[-1] == res[-2] and res[-2] == k:\n",
    "                    continue\n",
    "                find = True\n",
    "                res.append(k)\n",
    "                d[i][1] -= 1\n",
    "                break\n",
    "            if find == False:\n",
    "                return \"\".join(res)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        t = sorted([[a,'a'],[b,'b'],[c,'c']])\n",
    "        x,y,z,u,v,w = t[0][0],t[1][0],t[2][0],t[0][1],t[1][1],t[2][1]\n",
    "        return ((w+u)*x+(w+v)*y+w).replace(w,w*2,z-1-x-y) if z > x+y else (w+v+u)*(x+y-z)+(w+u)*(z-y)+(w+v)*(z-x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestDiverseString(self, a: int, b: int, c: int) -> str:\n",
    "        ans = []\n",
    "        cnt = [[a, 'a'], [b, 'b'], [c, 'c']]\n",
    "        while True:\n",
    "            cnt.sort(key=lambda x: -x[0])\n",
    "            hasNext = False\n",
    "            for i, (c, ch) in enumerate(cnt):\n",
    "                if c <= 0:\n",
    "                    break\n",
    "                if len(ans) >= 2 and ans[-2] == ch and ans[-1] == ch:\n",
    "                    continue\n",
    "                hasNext = True\n",
    "                ans.append(ch)\n",
    "                cnt[i][0] -= 1\n",
    "                break\n",
    "            if not hasNext:\n",
    "                return ''.join(ans)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
